Bitplane based coding methods are used for coding a variety of types of data. The term bitplane is generally used to refer to a set of bits having the same position in the binary numbers of a set of data. For example, for a set of 8 bit data values there would be 8 bitplanes with each bit of a data value corresponding to a single corresponding one of the 8 bitplane. The bitplane to which a bit in a data value corresponds is determined based on its position within the data value.
Bitplane coding has been applied to a wide variety of different types of data, e.g., audio data as well as image data.
Bitplane based coding methods often rely on entropy coding of the binary values which form a bitplane. One coding standard which uses bitplane coding is the JPEG 2000 standard.
JPEG 2000 (ISO/IEC 15444) is a recent standard of the ITU/ISO/IEC for compression of still images. A major obstacle in the widespread deployment and acceptance of JPEG 2000 is, however, its coding complexity. JPEG 2000 requires approximately ten times the computation time for compressing or decompressing an image than its predecessor, the JPEG standard (ISO/IEC 10918), did. While the coding scheme used in JPEG 2000 often results in better compression than the original JPEG standard, any methods for allowing JPEG 2000 compliant images to be generated by a coder in less time, even if it might reduce the achieved compression, would be desirable for many applications.
JPEG 2000 coders first run a wavelet transformation on the pixel levels of the image to be compressed, generating one or several so-called wavelet bands, each of which consists of wavelet-coefficients. In the lossy coding path, wavelet coefficients are quantized giving integer quantization indices which are then coded by the steps described below. In the lossless coding path, the wavelet transformation transforms integer pixel levels to integer wavelet coefficients without any loss and the integer coefficients are coded similar to the integer quantization indices in the lossy path. In both cases, the data v to be coded is represented as binary integers of N bits, consisting of a sign bit s(v)=0; 1 and N−1 magnitude bits mi(v)=0; 1 coding the numerical value v as
  υ  =                    (                  -          1                )                    s        ⁡                  (          υ          )                      ⁢                  ∑                  i          =          1                          N          -          1                    ⁢                                    m            i                    ⁡                      (            υ            )                          ⁢                  2                      N            -            1            -            i                              
The magnitude bits mi corresponding to the smaller i are called the most-significant bits or short MSBs, bits with higher indices are called the least significant bits, or short LSBs. The number of MSBs that are zero shall here be called the number of zero-bits, z, which is formally defined as:z(v):=maxi{mj(v)=0 for all j≦i}, where v is the wavelet coefficient represented in the binary sign-magnitude, coding defined above. Due to the nature of natural images, most wavelet coefficients are rather small, and thus z(v) is typically large.
For coding, JPEG 2000 separates the wavelet coefficients or quantization indices into rectangular regions called codeblocks, denoted by C in the following. In the next step, the coder typically determines the number of zero-planes p(C) for each codeblock C, i.e. the number of MSBs that are zero for all coefficients within C. Formally:p(C):=minvεCz(v)
The collection of p(C) for all codeblocks is then coded by a so-called Tag Tree coding algorithm that is described in more detail in the JPEG 2000 standard and of no further interest for this document.
The remaining bits of all coefficients within a codeblock, i.e. bitplanesi=p(C)+1 and larger, are then coded by the so-called EBCOT-coder: allmi(v) of vεC with i>p(C)are subject to this coding step. The EBCOT coder first re-orders the data m, into so-called bitplanes which are denoted as follows:
Bitplane number i of codeblock C, denoted by bi, is the set of all magnitude bits mi(v) of all coefficients v in C. While bi consists entirely of zero bits for i≦p(C) by definition and thus do not require any further coding, this is not the case for i>p(C); however, it is important to note that the EBCOT coding algorithm does not depend on this fact and is also able to code bitplanes bi that consist entirely of zero bits.
Each bitplane bi is coded in exactly one out of three so-called coding passes defined in the JPEG 2000 standard; the order in which the data mi in bi is coded, and in which coding pass a coefficient is coded is also denoted in the standard and of no further relevance. However, it is important that the EBCOT coder has two options of coding the bits bi in bitplane i.
In the JPEG 2000 during normal standard mode of entropy coding, all bitplanes and all coding passes undergo so-called entropy coding by an arithmetic coder. This coder tries to represent the bits as compactly as possible employing the statistics of the data, but this entropy coding algorithm has a certain complexity that increases the overall complexity of the coding process; consequently, the complexity of the decoder is also high since it has to reverse these steps to reconstruct the data correctly.
In normal use of the so-called bypass mode of entropy coding of JPEG 2000 which can be signaled in the JPEG 2000 bitstream, only the first three bitplanes are coded as described above, i.e. j=p(C)+1 to j=p(C)+3 are coded as in the standard mode of entropy coding. All remaining bitplanes are coded partially bypassing the arithmetic coder: If a bit bi is coded in either the first or the second coding pass, the bit is directly written to the output bitstream bypassing the entropy coding process, only bits in the third coding pass are still entropy coded.
Since bypassing the entropy coder avoids its complexity, coding in the bypass mode is less complex and faster, but also tends to lower the coding efficiency measured as the average number of bits required to represent an image pixel. This is because bits are not represented as compactly as possible. The bypass coding mode is an option offered by the JPEG 2000 standard and available for all JPEG 2000 coders and decoders; it is relevant for understanding the nature of this invention.
While the bypass mode of JPEG 2000 provides the possibly of some speed up as compared to the standard mode of JPEG 2000, it still requires the coding of 3 bitplanes in accordance with the standard entropy coding method. Since entropy coding is normally rather computationally complex, the requirement that three bitplanes be entropy coded in the manner used in the standard mode tends to bottleneck in terms of the speed at which JPEG 2000 compliant coding can be performed. While modifying the JPEG 2000 standard to drop the requirement that 3 bitplanes be coded in accordance with the standard mode entropy coding process would be one way to speed up the coding processes, this would require a modification to the JPEG 2000 standard and a change to the JPEG 2000 decoders to support such an option.
The processing time required to code JPEG 2000 images on many processors, e.g., cell phone processors, etc. which operate at relatively low speed or have relatively little processing power, has delayed the wide spread use and acceptance of the JPEG 2000 standard as well as other bitplane based coding methods.
It should be appreciated that there is a need for finding ways to speed up the JPEG coding process and/or other bitplane coding processes to make them more widely acceptable. Such methods may be desirable for many applications even if the new methods result in a lower degree of compression.
In view of the above discussion, it should be appreciated that there is a need for new and improved bitplane coding methods. While not necessary, it would be desirable if at least one approach to bitplane coding could be developed which could be used to generate a JPEG 2000 compliant bitstream but which allowed for coding to be performed in less time than the typical JPEG 2000 coding methods.